#ifndef __COMPOSITE_H__
#define __COMPOSITE_H__
/*
* 组合问题
* 例: leetcode 编号 77
*/

/*
* 题目一般为:
*	1.给出一个集合 n, 和一个大小 k
*	2.求出大小为 k 的组合
*/

/*
* 搜索过程示例:
* { 1, 2, 3, 4}, 要求计算大小为 2 的所有组合
*		            1 2 3 4
*      1-234        2-34     3-4    4
* 12-34 13-4 14  23-4  24    34
* 
* 如上述树形结构, 例如: 取 1, 余 234; 再取 2, 得 12 余 34。
* 此时 12 达到大小 2, 终止, 得到结果(即叶子节点), 其他节点也是如此。
*/

#include <vector>
#include <algorithm>
using namespace std;

void BackTracking(const vector<int>& n, int k, vector<int>& path, vector<vector<int>>& results, int startIndex = 0) {
	//终止条件, 当得到的结果 == k, 终止递归, 进行回溯
	if (path.size() == k) {
		results.push_back(path);
		return;
	}
	
	//单层搜索(宽度), i 表示为该层节点的每一个子孩子
	for (int i = startIndex; i < n.size(); i++) {
		path.push_back(n[i]);
		//深度
		BackTracking(n, k, path, results, i + 1);
		//回溯
		path.pop_back();
	}
}

/*
* 组合问题剪枝
*/

/*
* 例如: n = { 1, 2, 3, 4 }, k = 4
* 树形结构如下: 
*		            1 2 3 4
*      1-234        2-34     3-4    4
* ...	...			...		...		...
* 可以看到, 除了最左边(取 1), 其他均不能达到个数为 4 的组合, 应该进行剪枝
* 
*			1-234
*	12-32	13-4	14
* ...	...	...		...
* 用样的, 在 取1 余234 中, 也只需要保留最左边的路径
* 
* 从代码上, 应该从 for 循环部分开始修改, 判断哪一个子节点应该被选取, 如下实现:
*/
void BackTrackingWithClip(const vector<int>& n, int k, vector<int>& path, vector<vector<int>>& results, int startIndex = 0) {
	if (path.size() == k) {
		results.push_back(path);
		return;
	}

	//n.size() - (k - path.size()) + 1, 剪枝操作, 判断子节点是否被选取
	/*
	* k - path.size()
	* 表示还需要多少个元素, 才能达到 k
	* 
	* 例: n = 4, k = 3
	* 1, 2, 3, 4
	*    i
	* 当 i = 2, path.size() = 1时, 还需要 k - path.size() = 2 个元素
	* 
	* 那么在之后的递归中:
	* 下标至多能到 n.size() - (k - path.size())
	* 才能满足 k, 这里( + 1 )是为了补全下标
	*/
	for (int i = startIndex; i < n.size() - (k - path.size()) + 1; i++) {
		path.push_back(n[i]);
		BackTrackingWithClip(n, k, path, results, i + 1);
		path.pop_back();
	}
}

/*
* 组合总和
*/
/*
* Ⅰ.给出一个大小为 n 的集合, 求出总和为 m, 大小为 k 的所有组合。
*/
#include <numeric>
void BackTrackingAccumulateI(const vector<int>& n, vector<int>& path, vector<vector<int>>& results, int m, int k, int startIndex = 0) {
	if (path.size() == k) {
		if (accumulate(path.begin(), path.end(), 0) == m)
			results.push_back(path);

		return;
	}
	
	//剪枝
	if (accumulate(path.begin(), path.end(), 0) >= m)
		return;

	int size = n.size() - (k - path.size()) + 1;
	for (int i = startIndex; i < size; i++) {
		path.push_back(n[i]);
		BackTrackingAccumulateI(n, path, results, m, k, i + 1);
		path.pop_back();
	}
}

/*
* Ⅱ.给出一个集合 和 一个目标值, 找出一个组合, 使之等于目标值。
* 注意: 元素可以重复选取, 并且集合中的元素均为正整数
* 
* 这和组合总和Ⅰ不同, 树形结构的深度不容易体现
* 例: {2, 5, 3},  target = 4
* 
*					253
*		2-253		5-53		 3-33
* 22-253 25-53...	  ...			...
* 
* 如上述的树形结构
* 取 2, 余下253(可重复)。 取2, 得22, 余下253; 取5, 得25, 余下 53(225 和 252 重复)...
* 取 5, 余下 53 (25 和 52 重复) ...
* ...
* 当集合内结果为 target 时, 放入结果集中。
*/
void BackTrackingAccumulateII(const vector<int>& n, int target, vector<int>& path, vector<vector<int>>& results, int startIndex = 0) {
	if (accumulate(path.begin(), path.end(), 0) > target)
		return;

	if (accumulate(path.begin(), path.end(), 0) == target) {
		results.push_back(path);
		return;
	}

	for (int i = startIndex; i < n.size(); i++) {
		path.push_back(n[i]);
		BackTrackingAccumulateII(n, target, path, results, i);
		path.pop_back();
	}
}

/*
* III.给出一个集合(可能有重复元素) 和 一个目标 target, 要求获取所有结果为 target 的组合
* 另外, 关于最终的结果, 不能出现重复的组合。并且集合中的元素只能使用一次
* 
* 例如: n = { 10, 1, 2, 7, 6, 1, 5 }, target = 8
* {1, 7} 和 {7, 1} 都可以为结果, 但是重复了。
* 
* 研究一下树形结构, 以及如何进行去重:
*	n = { 1, 1, 2 }, target = 3
* 注意: 进行去重首先得将元素进行排序, 这里例子中的集合已经默认进行排序了
* 
* 首先定义一个 bool 类型的集合, 用于标记元素是否被使用 bUse = { false, false, false }
*							112
*		1-12(100)				1-2(010)	2-(001)
* 11-2(110)		12-(101)		12-(011)
* 
* 如上述树层结构: 
* 取 1, 余下 12, bUsed(100); 取 1(第二个), 余下 2, bUsed(010)...
* 取 1, 余下 2, bUsed(110); 取 2, 余下 空, bUsed(101)...
* 
* 下面介绍如何去重:
* 在这里介绍两个维度: 树层去重(宽度); 树枝去重(深度)
* 在上述树形结构中:
* 1.树枝存在重复, 是可以被允许的, 每条树枝可以代表树的深度, 而深度和集合中的元素相关, 所以是没问题的
* 
* 2.而树层则不同, 由于集合已经排序, 所以在同一层中出现重复元素时, 必定出现组合重复, 所以需要在树层的维度进行去重
*	此时 bUsed 就发挥作用了, 当该元素的前一个元素的 bUsed 为 false 时, 则可以判断为树层
*													 若为 true 时, 则是树枝, 不能进行去重
* 
* 在上述例子中, 在 1-2(101) 这个时, 同一层中选取了同样的元素, 需要进行去重, 否则后续会出现重复组合。
*/
void BackTrackingAccumulateIII(const vector<int>& n, int target, vector<int>& path, vector<bool>& bUsed, vector<vector<int>>& results, int startIndex = 0) {
	if (accumulate(path.begin(), path.end(), 0) > target)
		return;

	if (accumulate(path.begin(), path.end(), 0) == target) {
		results.push_back(path);
		return;
	}

	for (int i = startIndex; i < n.size(); i++) {
		//树层去重, 那么就写在 for 循环中
		if (i > 0 && !bUsed[i - 1] && n[i] == n[i - 1])
			continue;

		path.push_back(n[i]);
		bUsed[i] = true;
		BackTrackingAccumulateIII(n, target, path, bUsed, results, i + 1);
		path.pop_back();
		bUsed[i] = false;
	}
}

/*
* 电话号码的字母组合 (九宫格输入法)
*/
/*
* 输入九宫格中的数字, 列举出所有的字母组合
* 
* 例如: 输入数字 2 3, 树形结构如下
*				abc
*	 a-def		b-def	c-def
* ad ae af		....	....
* 
* 在 abc 中取 a(bc), 余下 def, 然后取 def 中的字母
* 结果在 叶子节点中
* 
* 树的深度由输入的数字决定, 宽度则是每个数字对应的字母数
*/
#include <string>
static vector<string> letterMap = {
	"", "", "abc", "def", "ghj", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
void BackTrackingLetter(const vector<int>& digits, string& path, vector<string>& result, int index = 0) {
	if (index == digits.size()) {
		result.push_back(path);
		return;
	}

	for (int i = 0; i < letterMap[digits[index]].size(); i++) {
		path.push_back(letterMap[digits[index]][i]);
		//在不同集合中进行组合, 不需要startIndex
		//树层结构的每一层表示为不同的集合, 只需要传入表示集合的 index 即可
		BackTrackingLetter(digits, path, result, index + 1);
		path.pop_back();
	}
}

#endif // !__COMPOSITE_H__

